// 392. 判断子序列
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */

/* 暴力 */
var isSubsequence = function (s, t) {
	let ret = true,
		prevIndex = 0
	for (let i = 0; i < s.length; i++) {
		const start = !i ? 0 : t[prevIndex] === s[i] ? prevIndex + 1 : prevIndex
		const index = t.indexOf(s.charAt(i), start)
		if (index === -1) {
			ret = false
			break
		}
		prevIndex = index
	}
	return ret
}
/* 双指针 */
var isSubsequence = function (s, t) {
	const n = s.length,
		m = t.length
	let i = 0,
		j = 0
	while (i < n && j < m) {
		if (s.charAt(i) === t.charAt(j)) {
			i++
		}
		j++
	}
	return i === n
}
/* dp */
var isSubsequence = function (s, t) {
	// s、t的长度
	const [m, n] = [s.length, t.length]
	/* 
        dp全初始化为0
        表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同序列的长度为dp[i][j]
    */
	const dp = new Array(m + 1).fill(0).map((x) => new Array(n + 1).fill(0))
	for (let i = 1; i <= m; i++) {
		for (let j = 1; j <= n; j++) {
			// 更新dp[i][j]，两种情况
			if (s[i - 1] === t[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1
			} else {
				/* 
                    t 需要删除元素
                    t 如果把当前元素删除，那么 dp[i][j] 的数值就要看
                    s[i-1] 与 t[j-2] 
                */
				dp[i][j] = dp[i][j - 1]
			}
		}
	}
	// 遍历结束，判断dp右下角的数是否等于s的长度
	return dp[m][n] === m ? true : false
}
const ret = isSubsequence('abc', 'ahbgdc')
console.log('isSubsequence :>>', ret)
